 1.动态规划之案例四
   
   0-1 背包问题
   有 n 件物品和一个最大承重为 W 的背包，每件物品的重量是 𝑥i、价值是 𝑤i
      在保证总重量不超过 W 的前提下，将哪几件物品装入背包，可以使得背包的总价值最大？
      注意：每个物品只有 1 件，也就是每个物品只能选择 0 件或者 1 件，因此这类问题也被称为 0-1 背包问题
   动态规划步骤
   设定 values 是价值数组，weights 是重量数组
   int[] values= {6,3,5,4,6};
   int[] weights={2,2,6,5,4};
   int capacity=10;   
   定义状态方程
   dp(i, j) 是 最大承重为 j、有前 i 件物品可选 时的最大总价值，i ∈ [0, n]，j ∈ [0, W]
   初始状态
   dp(i, 0)、dp(0, j) 初始值均为 0
   状态转移方程
   dp(i,j)=dp(i-1,j-1)
   如果只剩最后一件物品时，有两种情况
       不选择该物品：dp(i,j)=dp(i-1,j)
       选择该物品：dp(i,j)=values[i]+dp(i-1,j-weights[i])
   
   dp(i,j)返回的是最大总价值
   max(dp(i-1,j),values[i]+dp(i-1,j-weights[i]))
       如果 j < weights[i – 1]，那么 dp(i, j) = dp(i – 1, j)
       如果 j ≥ weights[i – 1]，那么 dp(i, j) = max { dp(i – 1, j), dp(i – 1, j – weights[i – 1]) + values[i – 1] }
   
   代码实现
package com.lg.dp;

/**
 * 使用动态规划解决01背包问题
 */
public class PackSack {
    public static void main(String[] args) {
        int[] values= {6,3,5,4,6};
        int[] weights={2,2,6,5,4};
        int capacity=10;
        System.out.println(getMaxVal(values, weights, capacity));
    }

    static int getMaxVal(int[] values, int[] weights, int capacity) {
        //过滤掉不合理的值
        if(values==null || values.length==0){return 0;}
        if (weights==null || weights.length==0){return 0;}
        if (capacity<0){return 0;}
        //使用递推方式:dp(i,j):最大承重为j，有前i件物品可选时的最大总价值
        int[][] dp=new int[values.length+1][capacity+1];//数组初始化默认值就是0
        //遍历
        for (int i = 1; i <= values.length; i++) {
            for (int j = 1; j <= capacity; j++) {
                //翻译状态转移方程
                if (j < weights[i-1]) {
                    dp[i][j]=dp[i-1][j];
                } else {
                    dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1]);
                }
            }
        }
        return dp[values.length][capacity];
    }
}
   递推实现思路分析
   第二版
   使用一维数组进行优化。
package com.lg.dp;

/**
 * 使用动态规划解决01背包问题
 */
public class PackSack1 {
    public static void main(String[] args) {
        int[] values= {6,3,5,4,6};
        int[] weights={2,2,6,5,4};
        int capacity=10;
        System.out.println(getMaxVal(values, weights, capacity));
    }

    static int getMaxVal(int[] values, int[] weights, int capacity) {
        //过滤掉不合理的值
        if(values==null || values.length==0){return 0;}
        if (weights==null || weights.length==0){return 0;}
        if (capacity<0){return 0;}
        //使用递推方式:dp(i,j):最大承重为j，有前i件物品可选时的最大总价值
        int[] dp=new int[capacity+1];//数组初始化默认值就是0
        //遍历
        for (int i = 1; i <= values.length; i++) {
            //改变为从右向左执行
            for (int j = capacity; j >= weights[i-1]; j--) {
                //翻译状态转移方程
                dp[j]=Math.max(dp[j], dp[j-weights[i-1]]+values[i-1]);
            }
        }
        return dp[capacity];
    }
}
   
   